/**
    ******************************************************************************
    * @file    sort.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-11-04
    * @brief   排序算法
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "sort.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "../link/link.h"

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup sort
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup sort_Exported_Functions sort Exported Functions
    * @{
    */

/** @defgroup sort_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the sort
        to be ready for use.
 
@endverbatim
    * @{
    */ 


/*****************************************/
/**********  冒泡排序       ******************/
/*****************************************/


/**
  * @brief  冒泡排序1
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int bubble_sort1(int *base, int len)
{
    int i = 0 , j = 0;
    int temp;
    for(i=0; i<len-1; i++)
    {
        for(j=0; j<len-i-1; j++)
        {
           if(base[j] > base[j+1])
           {
               temp = base[j];
               base[j] = base[j+1];
               base[j+1] = temp;
           }
        }
    }

    return 0;
}

//屏蔽
#if 0
typedef int (*COMPARE)(const void *e1, const void *e2);
static void byte_swap(void *pData1, void *pData2, int size)
{
    unsigned char *pcData1 = pData1;
    unsigned char *pcData2 = pData2;
    unsigned char temp;

    while(size--)
    {temp = *pcData1; *pcData1 = *pcData2; *pcData2=temp; pcData1++; pcData2++;}
}
int bubble_sort1(void *base, int len, int size, COMPARE compare)
{
    int i = 0 , j = 0;
    void *pThis;
    void *pNext;
    for(i=0; i<len-1; i++)
    {
        for(j=0; j<len-i-1; j++)
        {
            pThis = ((unsigned char *)base)+(j*size);
            pNext = ((unsigned char*)base)+(j+1)*size;            
            if(compare(pThis, pNext) > 0)
            {
                byte_swap(pThis, pNext, size);
            }
        }
    }
}
#endif

/**
  * @brief  冒泡排序2，优化有序之后还继续循环的问题
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int bubble_sort2(int *base, int len)
{
    int i = 0 , j = 0;
    int temp;
    int flag = 1;       //1是有序的
    for(i=0; i<len-1; i++)
    {
        flag = 1;       //初始默认是有序的
        for(j=0; j<len-i-1; j++)   //进入循环
        {
           if(base[j] > base[j+1])
           {
               flag = 0;                //这次循环无序的，标志置0
               temp = base[j];
               base[j] = base[j+1];
               base[j+1] = temp;
                
           }
           printf("sort_border %d\n", j);
        }
        if(flag == 1)               //如果是有序的就退出
            break;
    }

    return 0;
}


/**
  * @brief  冒泡排序3，在2的基础上，优化了右侧有序就不用循环了
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int bubble_sort3(int *base, int len)
{
    int i = 0 , j = 0;
    int k = 0;
    int temp;
    int flag = 1;       //1是有序的
    int sort_border = len-1;
    int sort_border_temp = sort_border;
    for(i=0; i<len-1; i++)
    {
        flag = 1;       //初始默认是有序的
        sort_border_temp = sort_border;            //需要每次初始化？
        for(j=0; j<sort_border_temp; j++)   //进入循环,循环判断条件
        {
           if(base[j] > base[j+1])
           {
               flag = 0;                //这次循环无序的，标志置0
               temp = base[j];
               base[j] = base[j+1];
               base[j+1] = temp;
               sort_border = j;
               
           }
            printf("sort_border %d %d\n", sort_border, j);
        }
        if(flag == 1)               //如果是有序的就退出
            break;
    }

    return 0;
}


/*****************************************/
/**********  选择排序       ******************/
/*****************************************/


/**
  * @brief  选择排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int select_sort(int *base, int len)
{
    int i = 0 , j = 0;
    int small_index = 0;
    int temp = 0;

    for(i=0; i<len-1; i++)
    {
        //small = base[i];            //每次循环，获取当前i上的值，作为默认最小值
        small_index = i;
        for(j=i+1; j<len; j++)        //进入循环,循环判断条件  因为 i已经在移动了，所以j<len就这样
        {
           if(base[j] < base[small_index])
           {
               //small = base[j];
               small_index = j;
           }
            printf("sort_border %d %d\n", small_index, j);
        }
       
        if(i != small_index)
        {
            temp = base[i];
            base[i] = base[small_index];
            base[small_index] = temp;             
        }
    }

    return 0;
}


/*****************************************/
/**********  插入排序       ******************/
/*****************************************/


/**
  * @brief  插入排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int insert_sort(int *base, int len)
{
    int i=0, j = 0;
    int temp = 0;
    for(i=1; i<=len-1; i++)
    {      
        temp = base[i];
        for ( j=i; temp<base[j-1]; j-- )
        {
            printf("i= %d %d %d\n", i, base[j], base[j-1]);
            base[j] = base[j-1];
        }

        if(j != i)
        {
            base[j] = temp;
        }
    }

    return 0;
}


/*****************************************/
/**********  希尔排序       ******************/
/*****************************************/


/**
  * @brief  希尔排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int shell_sort(int *base, int len)
{
    int i=0, j = 0;
    int temp = 0;
    int gap = len;                //增量

    //增量的定义可能不同，我们这里去/2
    for ( gap = len/2; gap >= 1; gap /= 2)
    {
        for ( i = gap; i < len; i++)
        {       
            temp = base[i];
            printf("gap = %d i = %d j = %d base[i] = %d base[j] = %d\n", gap, i, i-gap, base[i], base[i-gap]);
            for(j=i-gap; j>=0 && temp<base[j]; j-=gap)
            {
                printf("for gap = %d i = %d j = %d base[i] = %d base[j] = %d\n", gap, j+gap, j, base[j+gap], base[j]);
                base[j+gap] = base[j];
            }
            base[j+gap] = temp;
            bianli(base);
        }
    }

    return 0;
}



/*****************************************/
/**********  归并排序       ******************/
/*****************************************/

/**
  * @brief  归并
  * @param  base  : 数据的基地址
  *         temp  : 需要外部传入跟base大小一样的临时数组 
  *         start : 排序的首下标
  *         end   : 排序的结束下标
  * @retval 成功返回0，失败返回负数
  */
static int merge(int *base, int *temp, int start, int middle, int end)
{
    int i = 0, j = 0,k = start;
    
    printf("merge %d %d %d\n", start, middle, end);
    //归并
    for(i=start, j=middle+1; i<=middle && j<=end; k++)  //i=0, j=1; 
    {
        if(base[i] < base[j])   
        {
            temp[k] = base[i++];
        }
        else
        {
            temp[k] = base[j++];
        }
    }

    while(i<=middle)
    {
        temp[k++] = base[i++];
    }

    while(j<=end)
    {
        temp[k++] = base[j++];
    }

    //需要拷贝回到data中
    for(i=start; i<=end; i++)
    {
        base[i] = temp[i];
    }

    bianli(base);
    return 0;
}

/**
  * @brief  归并排序
  * @param  base  : 数据的基地址
  *         temp  : 需要外部传入跟base大小一样的临时数组 
  *         start : 排序的首下标
  *         end   : 排序的结束下标
  * @retval 成功返回0，失败返回负数
  */
int merge_sort(int *base, int *temp, int start, int end)
{
    //start开始下标，end结束下标
    int middle; 
    printf("start %d %d\n", start, end);
    if(start < end)
    {
        middle = start + (end-start)/2;   
        printf("middle %d %d %d\n", start, middle, end);
        merge_sort(base, temp, start, middle);  // 0 3  0 1    0 0
        printf("end %d %d %d\n", start, middle+1, end);   
        merge_sort(base, temp, middle+1, end);   //  4 7  2 3   1 1

        //排序，倒序归并排序
        printf(">>>>>>>>>>>>>>>>\n");
        merge(base, temp, start, middle, end);
    }
    printf("返回 \n");
    return 0;
}



/*****************************************/
/**********  快速排序       ******************/
/*****************************************/


/**
  * @brief  排序
  * @param  base    : 数据的基地址
  *         start   : 数据开始下标
  *         end     : 数据结束下标
  * @retval 成功返回0，失败返回负数
  */
static int partition(int *base, int start, int end)
{
    int pivot = start;          //选择基准元素，目前直接选择第一个元素
    int left = start, right = end;
    int temp = 0;

    while (left != right)
    {
        while(right > left && base[right] >= base[pivot])   //右边的元素大于等于基准元素，然后就继续往左走
        {
            right--;
        }

        while(right > left && base[left] <= base[pivot])   //右边的元素大于等于基准元素，然后就继续往左走
        {
            left++;
        }

        printf("right = %d left = %d\n", right, left);
        if(right > left)
        {
            temp = base[right];
            base[right] = base[left];
            base[left] = temp;
        }
        bianli(base);
    }
    
    //基准元素交换
    temp = base[left];
    base[left] = base[pivot];
    base[pivot] = temp;

    return left;
}


/**
  * @brief  从最左测和中间和最右测 分别提取3个数然后比较，中间的数移动到左测
  * @param  base    : 数据的基地址
  *         start   : 数据开始下标
  *         end     : 数据结束下标
  * @retval 成功返回0，失败返回负数
  */
static int get_median(int *base, int start, int end)
{
    int middle = start + (end - start)/2;
    int temp = 0;

    printf("get %d %d %d\n", base[start], base[middle], base[end]);
    if(base[start] > base[end])
    {
        temp = base[start];
        base[start] = base[end];
        base[end] = temp;
    }

    if(base[middle] > base[end])
    {
        temp = base[middle];
        base[middle] = base[end];
        base[end] = temp;
    }

    if(base[middle] > base[start])    //把中间的值赋给base[start]
    {
        temp = base[middle];
        base[middle] = base[start];
        base[start] = temp;
    }

    printf("get %d %d %d\n", base[start], base[middle], base[end]);
    return base[start];
}


/**
  * @brief  排序1
  * @param  base    : 数据的基地址
  *         start   : 数据开始下标
  *         end     : 数据结束下标
  * @retval 成功返回0，失败返回负数
  */
static int partition1(int *base, int start, int end)
{
    int pivotKey = base[start];          //选择基准元素，目前直接选择第一个元素
    int left = start, right = end;
    int temp = 0;

    pivotKey = get_median(base, start, end);

    while (left != right)
    {
        while(right > left && base[right] >= pivotKey)   //右边的元素大于等于基准元素，然后就继续往左走
        {
            right--;
        }

        base[left] = base[right];       //直接赋值给left的位置

        while(right > left && base[left] <= pivotKey)   //右边的元素大于等于基准元素，然后就继续往左走
        {
            left++;
        }

        base[right] = base[left];       //往右走的直接赋值给right 

        printf("right = %d left = %d\n", right, left);
        bianli(base);
    }
    
    //基准元素交换
    base[left] = pivotKey;

    return left;
}


/**
  * @brief  快速排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int quick_sort(int *base, int start, int end)
{
    int pivot; 
    
    if(start < end)
    {
        pivot = partition1(base, start, end);        //分为两段，并返回基准元素

        printf("pivot = %d\n", pivot);
        quick_sort(base, start, pivot-1);
        quick_sort(base, pivot+1, end);
    }
  
    return 0;
}



/*****************************************/
/**********  堆排序        ******************/
/*****************************************/

/**
  * @brief  构造大顶堆
  * @param  base: 数据的基地址
  *			parent : 父节点
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
static int heap_adjust(int *base, int parent, int len)
{
	int child = parent*2+1;
	int temp = base[parent];			//先保存起来，现在比较喜欢玩这种

	while(child<len)     //二叉树的遍历性质，2*s是其左孩子
	{
		//找到最大的孩子,需要比较，怕超出范围
		if((child+1<len) & (base[child+1] > base[child]))
		{
			++child;
		}

		//比较最大的孩子和父亲比较，如果孩子大交换，否则返回
		if(base[child] <= temp)
			break;

		//交换
		base[parent] = base[child];   //child = 7
		parent = child;
		child = parent*2+1;			  //如果是前面的结点就继续往下遍历
	}
	
	base[parent] = temp;
	bianli(base);
	return 0;
}

/**
  * @brief  堆排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int heap_sort(int *base, int len)
{
	int i = 0;
	int temp = 0;
	int end = 0;
	//第一步:构造大顶堆
	for(i=(len-2)/2; i>=0; i--)
	{
		heap_adjust(base, i, len);    //(8-2)/2=3  从最低部开始构造，大顶堆是每一个结点的值都大于或等于其孩子的值
	}
	

	//第二步：循环移动最大值，然后继续构造大顶堆
	for(end=len-1;end>0;end--)
	{
		//移走最大值
		temp = base[0];
		base[0] = base[end];
		base[end] = temp;

		//剩下的继续构造大顶堆
		heap_adjust(base, 0, end);   //从堆顶开始构造，因为现在有一半是有序了
	}
	
    return 0;
}



/*****************************************/
/**********  计数排序       ******************/
/*****************************************/

/**
  * @brief  计数排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
int count_sort(int *base, int len)
{
	int i = 0, j = 0, index = 0;
	//1.找到最大值和最小值
	int max = base[0];   //定义0为最大值和最小值
	int min = base[0];
	int count = 0;
	int *count_arr = NULL;
	for(i=1;i<len;i++)
	{
		if(base[i]>max)
		{
			max = base[i];    //查找最大值
		}

		if(base[i]<min)
		{
			min = base[i];		//查找最小值
		}
	}
	printf("max %d %d\n", max, min);
	//2.创建统计数组
	count = max - min + 1;			//计数数组的长度
	count_arr = (int*)malloc(count*sizeof(int));
	if(count_arr == NULL)
		return -1;
	memset(count_arr, 0, count*sizeof(int));
	bianli(count_arr);
	//3.填充统计数组
	for(i=0;i<len;i++)
	{
		count_arr[base[i]-min]++;
	}
	bianli(count_arr);
	//4.输出原来的数组
	for(i=0;i<count;i++)   //遍历计数数组
	{
		for(j=0;j<count_arr[i];j++)   //查看每一个有值的元素，就是个数，所以需要循环
		{
			base[index++] = i+min;	  //填充到原来的数组中，记得加偏移
		}
	}
	
	return 0;
}


/*****************************************/
/**********  桶排序    **********************/
/*****************************************/

/**
  * @brief  桶排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
struct single_link *g_bucket_arr[10];

int bucket_sort(double *base, int len)
{
	int i = 0, j = 0, index = 0;
	
	//1.找到最大值和最小值
	double max = base[0];   //定义0为最大值和最小值
	double min = base[0];
	double d = 0;
	//double *bucket_arr = NULL;
	int bucket_index = 0;
	int bucket_len = 0;
	for(i=1;i<len;i++)
	{
		if(base[i]>max)
		{
			max = base[i];    //查找最大值
		}

		if(base[i]<min)
		{
			min = base[i];		//查找最小值
		}
	}
	d = max - min;			//计算差值
	printf("max %lf %lf\n", max, min);
	
	//2.初始化桶，每一桶相当于链表的头节点
	bucket_len = len;				//不同的桶的数量可以修改
	//申请头节点指针存储的位置
	//struct single_link *bucket_arr = (struct single_link*)malloc(bucket_len*4);   //申请链表头节点数组
	//if(bucket_arr == NULL)
	//	return -1;

	//每一个桶都存放着一个链表的头节点
	for(i=0;i<bucket_len;i++)
	{
		//printf("2. %d %p %p\n", i, bucket_arr, &(bucket_arr[i]));
		single_link_creat(&g_bucket_arr[i]);
	}

	printf("3.binali\n");
	//3.遍历原始数列，并保存到桶中
	for(i=0;i<len;i++)
	{
		//printf("3. ji = %lf %lf\n", base[i]-min, (max-min)/(bucket_len-1));
		bucket_index = (int)((base[i]-min) / ((max-min)/(bucket_len-1)));
		printf("3. bucket_index = %lf %d\n", base[i], bucket_index);
 		single_link_Sequential_insert_add(g_bucket_arr[bucket_index], base[i]);   //新加函数，按顺序插入列表
	}

	//遍历测试
	for(i=0;i<5;i++)
		single_link_bainli(g_bucket_arr[i]);

	//4.对每一个桶内部元素排序
	//上一步已经做了，这次就不需要了
	printf("4.最后\n");
	//5.遍历桶，输出元素
	for(i=0;i<bucket_len;i++)   //遍历桶
	{
		struct single_link * pNext = g_bucket_arr[i]->next;
		for(j=0;j<single_link_length(g_bucket_arr[i]);j++)   //查看每一个桶里面是否有元素(第一个data数据就是长度)，有就填充到原来的数组
		{
			//printf("ggg %d %d %lf\n", i, j, pNext->data);
			base[index++] = pNext->data;
			pNext = pNext->next;
			//printf("jiegu %d %lf\n", index-1, base[index-1]);
		}
	}
	
	return 0;
}



/*****************************************/
/**********  基数排序    **********************/
/*****************************************/

/**
  * @brief  基数排序
  * @param  base: 数据的基地址
  *         len : 数据的长度
  * @retval 成功返回0，失败返回负数
  */
#define RADIX 10
#define MAX 20
struct single_link *g_radix_arr[MAX];

int radix_sort(int *base, int len)
{
	int i = 0;
	int exp = 1;
	//1.创建10个空桶（基数为10，所以10个）
	//因为是c语言，不好创建，直接用全局变量了
	for(i=0;i<MAX;i++)
	{
		single_link_creat(&g_radix_arr[i]);
	}

	//2.获取有最大值有几个位
	int max = abs(base[0]);
	for(i=1;i<len;i++)
	{
		if(abs(base[i]) > max)
			max = abs(base[i]);
	}

	//3.开始排序，以最大值每次都除以10/100类推
	while(max / exp > 0)
	{
		printf("radix_sort %d\n", max/exp);

		//第一次是个位排序
		//查看哪个下标，然后填入
		for(i=0;i<len;i++)
		{
			printf("shu %d %d\n", base[i], base[i]/exp%RADIX+RADIX);
			single_link_Sequential_insert_add(g_radix_arr[base[i]/exp%RADIX+RADIX], base[i]);
		}

		//链表测试
		for(i=0;i<10;i++)
		{
			printf("bainli %d\n", i);
			single_link_bainli(g_radix_arr[i]);
		}
			

		//准备下一次排序数组	
		int index = 0, len = 0;
		for(i=0;i<MAX;i++)
		{
			single_link_get(g_radix_arr[i], &base[index], MAX, &len);
			single_link_delete(g_radix_arr[i]);
			index += len;
		}
		
		bianli(base);
		exp *= RADIX;
	}

	return 0;
}



void bianli(int *data)
{
    int i = 0;
    for(i=0; i<10; i++)
    {
        printf("%ld ", data[i]);
    }
    printf("\n");
}

int main()
{
    int i = 0;
    //int data[] = {3, 1, 0, 2, 4, 5, 6, 7};
    int data[] = {5, 8, 4, 3, 9, 2, 1, 7};
    int temp[8] = {0};
	//double xiaoshu[] = {4.5, 0.84, 3.25, 2.18, 0.5, 1.1, 9.8, 23};
	double xiaoshu[] = {4.5, 0.84, 3.25, 2.18, 0.5};
	int data1[] = {64, -8, 16, -512, -27, -729, 0, 1, 43, 25};

	printf("hahah\n");
    //shell_sort(data, sizeof(data)/sizeof(data[0]));
   // bubble_sort1(data, sizeof(data)/sizeof(data[0]), 4, int_compaer);
   //merge_sort(data, temp, 0, sizeof(data)/sizeof(data[0])-1);
   //quick_sort(data, 0, sizeof(data)/sizeof(data[0])-1);
	//heap_sort(data, sizeof(data)/sizeof(data[0]));
	//count_sort(data, sizeof(data)/sizeof(data[0]));
	//bucket_sort(xiaoshu, sizeof(xiaoshu)/sizeof(xiaoshu[0]));
	radix_sort(data1, sizeof(data1)/sizeof(data1[0]));
	

    for(i=0; i<10; i++)
    {
        printf("%d ", data1[i]);
    }


    return 0;

}


    
/**
    * @}
    */

/** @defgroup sort_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the sort.

@endverbatim
    * @{
    */

        /* 操作函数写在这里 */

    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

